package io.gitee.xyuesheng.day02;

import org.junit.Test;

import java.util.Arrays;

public class HomeworkClassSort {
    //冒泡排序
    @Test
    public void testBubble() {
        int[] a = {5, 4, 7, 3, 1, 2, 6};
        System.out.println(Arrays.toString(bubble(a)));
    }

    public static int[] bubble(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }

    //选择排序
    @Test
    public void testSelection() {
        int[] a = {5, 4, 8, 3, 1, 2, 6};
        System.out.println(Arrays.toString(selection(a)));
    }

    public static int[] selection(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
        return array;
    }

    //插入排序
    @Test
    public void testInsertion() {
        int[] a = {5, 4, 9, 3, 1, 2, 6};
        System.out.println(Arrays.toString(insertion(a)));
    }

    public static int[] insertion(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
        return array;
    }

    //归并排序
    @Test
    public void testMerge() {
        int[] a = {5, 4, 8, 3, 1, 7, 6};
        System.out.println(Arrays.toString(merge(a, 0, a.length - 1)));
    }

    public static int[] merge(int[] array, int l, int h) {
        if (l == h) {
            return new int[]{array[l]};
        }
        int mid = l + (h - l) / 2;
        int[] leftArr = merge(array, l, mid);
        int[] rightArr = merge(array, mid + 1, h);
        int[] newNum = new int[leftArr.length + rightArr.length];
        int m = 0, i = 0, j = 0;
        while (i < leftArr.length && j < rightArr.length) {
            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < leftArr.length)
            newNum[m++] = leftArr[i++];
        while (j < rightArr.length)
            newNum[m++] = rightArr[j++];
        return newNum;
    }

    //快速排序
    @Test
    public void testQuick() {
        int[] a = {5, 4, 8, 3, 9, 2, 6};
        System.out.println(Arrays.toString(quick(a, 0, a.length - 1)));
    }

    public static int[] quick(int[] array, int start, int end) {
        int pivot = array[start];
        int i = start;
        int j = end;
        while (i < j) {
            while ((i < j) && (array[j] > pivot)) {
                j--;
            }
            while ((i < j) && (array[i] < pivot)) {
                i++;
            }
            if ((array[i] == array[j]) && (i < j)) {
                i++;
            } else {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        if (i - 1 > start) array = quick(array, start, i - 1);
        if (j + 1 < end) array = quick(array, j + 1, end);
        return array;
    }


}
